import java.util.Deque;
import java.util.LinkedList;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: mirac
 * Date: 2025-09-01
 * Time: 12:23
 */
public class Sort {


    //交换
    private static void swap(int[] arr,int i,int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    //快速排序_三树取中法优化 + 小范围直接插入排序优化
    public static void quickSort(int[] arr) {
        //quick(arr,0,arr.length - 1);
        quickNor(arr,0,arr.length - 1);
    }

    //通过非递归实现
    //使用栈来存储待排序的子数组
    private static void quickNor(int[] arr,int start,int end) {
        Deque<Integer> stack = new LinkedList<>();
        int pivot = partitionHoare(arr,start,end);

        
        if (pivot > start + 1) {
            stack.push(start);
            stack.push(pivot - 1);
        }

        if (pivot < end - 1) {
            stack.push(pivot + 1);
            stack.push(end);
        }

        while (!stack.isEmpty()) {
            end = stack.pop();
            start = stack.pop();
            pivot = partitionHoare(arr,start,end);

            if (pivot > start + 1) {
                stack.push(start);
                stack.push(pivot - 1);
            }

            if (pivot < end - 1) {
                stack.push(pivot + 1);
                stack.push(end);
            }
        }
    }

    //通过递归实现
    private static void quick(int[] arr,int start,int end) {
        if (start >= end) {
            return;
        }

        if (end - start + 1 <= 7) {
            insertSort(arr,start,end);
            return;
        }

        int mid = getMiddleNum(arr,start,end);
        swap(arr,mid,start);

        int pivot = partitionHoare(arr,start,end);
        quick(arr,start,pivot - 1);
        quick(arr,pivot + 1,end);
    }
    //三数取中法
    private static int getMiddleNum(int[] arr,int left,int right) {
        int mid = (left + right)/2;
        if (arr[left] < arr[right]) {
            if (arr[mid] < arr[left]) {
                return left;
            }else if (arr[mid] > arr[right]) {
                return right;
            }else {
                return mid;
            }
        }else {
            if (arr[mid] < arr[right]) {
                return right;
            }else if (arr[mid] > arr[left]) {
                return left;
            }else {
                return mid;
            }
        }
    }

    //直接插入排序_范围
    public static void insertSort(int[] arr,int left,int right) {
        for (int i = left + 1; i <= right; i++) {
            int temp = arr[i];
            int j = i - 1;
            for (; j >= left; j--) {
                if (arr[j] > temp) {
                    arr[j + 1] = arr[j];
                }else {
                    arr[j + 1] = temp;
                    break;
                }
            }
            arr[j + 1] = temp;
        }
    }

    //霍尔法
    private static int partitionHoare(int[] arr,int left,int right) {
        int temp = arr[left];
        int tempLeft = left;
        while (left < right) {
            while (left < right && arr[right] >= temp) {
                right--;
            }
            while (left < right && arr[left] <= temp) {
                left++;
            }
            swap(arr,left,right);
        }
        swap(arr,left,tempLeft);
        return left;
    }
}
